package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-06
 * Time:13:57
 */

import java.util.*;

/**
 *
 牛客算法篇:BM41 输出二叉树的右视图
 描述
 请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
 数据范围： 0≤n≤100000≤n≤10000
 要求： 空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：
 所以对应的输出为[1,3,5]。
 示例1
 输入：
 [1,2,4,5,3],[4,2,5,1,3]
 返回值：
 [1,3,5]

 */
public class solve {
    public static void main(String[] args) {
        int[] preOrder = {1, 2, 4, 8, 9, 5, 3, 6, 7, 10};
        int[] inOrder = {8, 4, 9, 2, 5, 1, 6, 3, 7, 10};

        solve(preOrder,inOrder);
    }
    public static int[] solve(int[] preOrder, int[] inOrder) {
        List<Integer> result = new ArrayList<>();
        if (preOrder == null || inOrder == null || preOrder.length == 0 ||
                inOrder.length == 0) {
            return new int[0];
        }

        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < inOrder.length; i++) {
            indexMap.put(inOrder[i], i);
        }

        TreeNode root = buildTree(preOrder, 0, preOrder.length - 1, inOrder, 0,
                inOrder.length - 1, indexMap);

        if (root == null) {
            return new int[0];
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) {
                    result.add(node.val);
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }

        return res;
    }

    private static TreeNode buildTree(int[] preOrder, int preStart, int preEnd,
                                      int[] inOrder, int inStart, int inEnd, Map<Integer, Integer> indexMap) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        int rootVal = preOrder[preStart];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = indexMap.get(rootVal);
        int leftSize = rootIndex - inStart;

        root.left = buildTree(preOrder, preStart + 1, preStart + leftSize, inOrder,
                inStart, rootIndex - 1, indexMap);
        root.right = buildTree(preOrder, preStart + leftSize + 1, preEnd, inOrder,
                rootIndex + 1, inEnd, indexMap);

        return root;
    }
}
